{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Populating Next Right Pointers in Each Node II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #linked-list #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #链表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: connect"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #填充每个节点的下一个右侧节点指针 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树：</p>\n",
    "\n",
    "<pre>\n",
    "struct Node {\n",
    "  int val;\n",
    "  Node *left;\n",
    "  Node *right;\n",
    "  Node *next;\n",
    "}</pre>\n",
    "\n",
    "<p>填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 <code>NULL</code> 。</p>\n",
    "\n",
    "<p>初始状态下，所有&nbsp;next 指针都被设置为 <code>NULL</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/02/15/117_sample.png\" style=\"width: 500px; height: 171px;\" />\n",
    "<pre>\n",
    "<strong>输入</strong>：root = [1,2,3,4,5,null,7]\n",
    "<strong>输出：</strong>[1,#,2,3,#,4,5,7,#]\n",
    "<strong>解释：</strong>给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在范围 <code>[0, 6000]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你只能使用常量级额外空间。</li>\n",
    "\t<li>使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度。</li>\n",
    "</ul>\n",
    "\n",
    "<ul>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [populating-next-right-pointers-in-each-node-ii](https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [populating-next-right-pointers-in-each-node-ii](https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,null,7]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        nodes = [root]\n",
    "        while nodes:\n",
    "            new_nodes = []\n",
    "            for i in range(len(nodes)-1):\n",
    "                nodes[i].next = nodes[i+1]\n",
    "                if nodes[i].left:\n",
    "                    new_nodes.append(nodes[i].left)\n",
    "                if nodes[i].right:\n",
    "                    new_nodes.append(nodes[i].right)\n",
    "            if nodes[-1].left:\n",
    "                new_nodes.append(nodes[-1].left)\n",
    "            if nodes[-1].right:\n",
    "                new_nodes.append(nodes[-1].right)\n",
    "            nodes = new_nodes\n",
    "        return root\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            last = None\n",
    "            for i in range(size):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                if last:\n",
    "                    last.next = node\n",
    "                last = node\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root : return root\n",
    "        q = [root]\n",
    "        \n",
    "        while q:\n",
    "            \n",
    "            nxt = []\n",
    "            for i, node in enumerate(q):\n",
    "                if i == len(q)-1:\n",
    "                    node.next = None\n",
    "                else:\n",
    "                    node.next = q[i+1]\n",
    "                if node.left: nxt.append(node.left)\n",
    "                if node.right: nxt.append(node.right)\n",
    "            q = nxt\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if  not root:\n",
    "            return root\n",
    "        \n",
    "\n",
    "        def dfs(layer):\n",
    "            next_layer = []\n",
    "\n",
    "            for i in layer:\n",
    "                if i.left:\n",
    "                    next_layer.append(i.left)\n",
    "                if i.right:\n",
    "                    next_layer.append(i.right)\n",
    "            \n",
    "            for i in range(len(next_layer)-1):\n",
    "                next_layer[i].next = next_layer[i+1]\n",
    "            if next_layer:\n",
    "                dfs(next_layer)\n",
    "        dfs([root])\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        most_right = []\n",
    "\n",
    "        def walk(depth, tmp):\n",
    "            if tmp is None:\n",
    "                return\n",
    "\n",
    "            if len(most_right) < depth + 1:\n",
    "                most_right.append(tmp)\n",
    "            else:\n",
    "                most_right[depth].next = tmp\n",
    "                most_right[depth] = tmp\n",
    "            \n",
    "            walk(depth+1, tmp.left)\n",
    "            walk(depth+1, tmp.right)\n",
    "\n",
    "        walk(0, root)\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not root:\n",
    "            return root\n",
    "        q = [root]\n",
    "        while q:\n",
    "            temp = q\n",
    "            q = []\n",
    "            n = len(temp)\n",
    "            if n >= 2:\n",
    "                left, right = 0, 1\n",
    "                while right < n:\n",
    "                    temp[left].next = temp[right]\n",
    "                    if temp[left].left:\n",
    "                        q.append(temp[left].left)\n",
    "                    if temp[left].right:\n",
    "                        q.append(temp[left].right)\n",
    "                    left += 1\n",
    "                    right += 1\n",
    "                # left += 1\n",
    "                if temp[left].left:\n",
    "                    q.append(temp[left].left)\n",
    "                if temp[left].right:\n",
    "                    q.append(temp[left].right)\n",
    "            elif temp[0] is not None:\n",
    "                if temp[0].left:\n",
    "                    q.append(temp[0].left)\n",
    "                if temp[0].right:\n",
    "                    q.append(temp[0].right)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        pre = []\n",
    "        def dfs(node: 'Node', depth: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if depth == len(pre):  # node 是这一层最左边的节点\n",
    "                pre.append(node)\n",
    "            else:  # pre[depth] 是 node 左边的节点\n",
    "                pre[depth].next = node  # node 左边的节点指向 node\n",
    "                pre[depth] = node\n",
    "            dfs(node.left, depth + 1)\n",
    "            dfs(node.right, depth + 1)\n",
    "        dfs(root, 0)  # 根节点的深度为 0\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        # if not root:\n",
    "        #     return root\n",
    "\n",
    "        # queue = deque()\n",
    "        # queue.append(root)\n",
    "        # while queue:\n",
    "        #     size = len(queue)\n",
    "        #     for i in range(size):\n",
    "        #         node = queue.popleft()\n",
    "        #         if i < size -1:\n",
    "        #             node.next = queue[0]\n",
    "\n",
    "        #         if node.left:\n",
    "        #             queue.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             queue.append(node.right)\n",
    "        # return root\n",
    "\n",
    "\n",
    "        # if not root:\n",
    "        #     return root\n",
    "        # cur = root\n",
    "        # while cur:\n",
    "        #     dummyHead = Node(-1)\n",
    "        #     pre = dummyHead\n",
    "        #     while cur:\n",
    "        #         # 连接下一行的节点\n",
    "        #         if cur.left:\n",
    "        #             pre.next = cur.left\n",
    "        #             pre = pre.next\n",
    "        #         if cur.right:\n",
    "        #             pre.next = cur.right\n",
    "        #             pre = pre.next\n",
    "\n",
    "        #         cur = cur.next\n",
    "        #         if cur:\n",
    "        #             print(cur.val)\n",
    "        #     # 换行操作，更新到下一行\n",
    "        #     cur = dummyHead.next\n",
    "        #     if cur:\n",
    "        #         print(\"----------\",cur.val)\n",
    "\n",
    "        # return root\n",
    "\n",
    "\n",
    "        if not root:\n",
    "            return root\n",
    "        ro = root    \n",
    "        # 使用临时变量curLevel存储下一层的空头节点\n",
    "        # 空头节点的艺术: 1,使得代码得到统一，队头也不需要额外判断是否加pre; 2，实现了自动找行头，而不用单独加if判断\n",
    "        curLevel = Node()\n",
    "        root.next = None\n",
    "        # pre 存储前一个元素\n",
    "        pre = curLevel\n",
    "        # 使用节点的循环，不区分层内还是层间\n",
    "        while root:\n",
    "            if root.left:\n",
    "                pre.next= root.left\n",
    "                pre = root.left\n",
    "            if root.right:\n",
    "                pre.next = root.right\n",
    "                pre = root.right\n",
    "            root = root.next\n",
    "\n",
    "            # 当层末尾\n",
    "            if not root:\n",
    "                # 下层结尾\n",
    "                pre.next = None\n",
    "                # 转为处理下层\n",
    "                root = curLevel.next\n",
    "                if root:\n",
    "                    print(\"daa\",root.val)\n",
    "                print(pre.val)\n",
    "                print(curLevel.val)\n",
    "                pre = curLevel\n",
    "\n",
    "        return ro       \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "      \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        que = []\n",
    "        if root:\n",
    "            que.append(root)\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            last = None\n",
    "            for _ in range(size):\n",
    "                node = que.pop(0)\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "                if last:\n",
    "                    last.next = node\n",
    "                last = node\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        root.next = None\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            n = len(stack)\n",
    "            temp = []\n",
    "            for index, node in enumerate(stack):\n",
    "                node.next = stack[index+1] if index + 1 < n else None\n",
    "                if node.left:\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    temp.append(node.right)\n",
    "            stack = temp\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if i < size-1:\n",
    "                    cur.next = queue[0]\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:return None\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                node.next = q[0] if i < size-1 else None\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        pre = []\n",
    "        def dfs(node:Node,depth:int)->None:\n",
    "            if node is None:\n",
    "                return \n",
    "            if  depth == len(pre):\n",
    "                pre.append(node)\n",
    "            else:\n",
    "                pre[depth].next =  node\n",
    "                pre[depth] = node\n",
    "            dfs(node.left ,depth+1)\n",
    "            dfs(node.right,depth+1)\n",
    "        dfs(root,0)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        cur = root\n",
    "        while cur:\n",
    "            nxt = dummy = ListNode()\n",
    "            while cur:\n",
    "                if cur.left:\n",
    "                    nxt.next = cur.left\n",
    "                    nxt = cur.left\n",
    "                if cur.right:\n",
    "                    nxt.next = cur.right\n",
    "                    nxt = cur.right\n",
    "                cur = cur.next\n",
    "            cur = dummy.next\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root:\n",
    "            treestack = [root]\n",
    "            last = root\n",
    "            layer = 0\n",
    "            while len(treestack) != 0:\n",
    "                delete =  treestack[0]\n",
    "                if delete.left:\n",
    "                    treestack.append(delete.left)\n",
    "                if delete.right:\n",
    "                    treestack.append(delete.right)\n",
    "                if treestack[0] == last:\n",
    "                    treestack[0].next = None\n",
    "                    layer += 1\n",
    "                    last = treestack[-1]\n",
    "                    for i in range(1,len(treestack)-1):\n",
    "                        treestack[i].next = treestack[i+1]\n",
    "                treestack.pop(0)\n",
    "            return root\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "        head = root\n",
    "        while head:\n",
    "            next_head = None\n",
    "            pre = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                if cur.left and next_head is None:\n",
    "                    next_head = cur.left\n",
    "                if cur.right and next_head is None:\n",
    "                    next_head = cur.right\n",
    "                \n",
    "                if cur.left :\n",
    "                    if pre:\n",
    "                        pre.next = cur.left\n",
    "                    pre = cur.left\n",
    "                if cur.right:\n",
    "                    if pre:\n",
    "                        pre.next = cur.right\n",
    "                    pre = cur.right\n",
    "                cur = cur.next\n",
    "            head = next_head\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            last = None\n",
    "            for _ in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                if last:\n",
    "                    last.next = node\n",
    "                last = node\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        result = []\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            prev = None\n",
    "\n",
    "            for _ in range(level_size):\n",
    "                node = queue.popleft()\n",
    "                if prev:\n",
    "                    prev.next = node\n",
    "                \n",
    "                prev = node\n",
    "\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        q = [root]\n",
    "        while q:\n",
    "            for x,y in pairwise(q):\n",
    "                x.next = y\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left :\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        root.next = None\n",
    "        tmp0 = [root]\n",
    "        while tmp0:\n",
    "            tmp1 = []\n",
    "            for t in tmp0:\n",
    "                if t.left:\n",
    "                    tmp1.append(t.left)\n",
    "                if t.right:\n",
    "                    tmp1.append(t.right)\n",
    "            for i in range(len(tmp1)-1):\n",
    "                tmp1[i].next = tmp1[i+1]\n",
    "            tmp0 = tmp1\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        q = [root]\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            q1 = []\n",
    "            for i, x in enumerate(q):\n",
    "                if i < l-1:\n",
    "                    x.next = q[i+1]\n",
    "                if x.left:\n",
    "                    q1.append(x.left)\n",
    "                if x.right:\n",
    "                    q1.append(x.right)\n",
    "            q = q1\n",
    "        return root\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        pre = []\n",
    "        def dfs(node, depth):\n",
    "            if node is None:return\n",
    "            if depth == len(pre):\n",
    "               pre.append(node)\n",
    "            else:\n",
    "                pre[depth].next = node \n",
    "                pre[depth] = node \n",
    "            dfs(node.left, depth + 1)\n",
    "            dfs(node.right, depth + 1)\n",
    "        dfs(root, 0)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        pre = []\n",
    "        def dfs(node: 'Node', depth: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if depth == len(pre):  # node 是这一层最左边的节点\n",
    "                pre.append(node)\n",
    "            else:  # pre[depth] 是 node 左边的节点\n",
    "                pre[depth].next = node  # node 左边的节点指向 node\n",
    "                pre[depth] = node\n",
    "            dfs(node.left, depth + 1)\n",
    "            dfs(node.right, depth + 1)\n",
    "        dfs(root, 0)  # 根节点的深度为 0\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return root\n",
    "        Q = deque([root])\n",
    "        while Q:\n",
    "            size = len(Q)\n",
    "            for i in range(size):\n",
    "                node = Q.popleft()\n",
    "                if i < size - 1:\n",
    "                    node.next = Q[0]\n",
    "                if node.left:\n",
    "                    Q.append(node.left)\n",
    "                if node.right:\n",
    "                    Q.append(node.right)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        queue = collections.deque([root])\n",
    "        \n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            prev = None\n",
    "            \n",
    "            for i in range(level_size):\n",
    "                node = queue.popleft()\n",
    "                \n",
    "                if prev:\n",
    "                    prev.next = node\n",
    "                \n",
    "                prev = node\n",
    "                \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        start = root\n",
    "        while start:\n",
    "            self.last = None\n",
    "            self.nextStart = None\n",
    "            p = start\n",
    "            while p:\n",
    "                if p.left:\n",
    "                    self.handle(p.left)\n",
    "                if p.right:\n",
    "                    self.handle(p.right)\n",
    "                p = p.next\n",
    "            start = self.nextStart\n",
    "        return root\n",
    "\n",
    "    def handle(self, p):\n",
    "        if self.last:\n",
    "            self.last.next = p\n",
    "        if not self.nextStart:\n",
    "            self.nextStart = p\n",
    "        self.last = p\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        def get_node(node,deepth, store):\n",
    "            if not node:\n",
    "                return \n",
    "            store.setdefault(deepth,[])\n",
    "            store[deepth].append(node)\n",
    "            \n",
    "            get_node(node.left, deepth+1,store) if node.left else None\n",
    "            get_node(node.right, deepth+1,store) if node.right else None\n",
    "        \n",
    "        store = {}\n",
    "        get_node(root,0, store)\n",
    "        for i,nodes in store.items():\n",
    "            for i in range(len(nodes)-1):\n",
    "                nodes[i].next = nodes[i+1]\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    pre = []\n",
    "\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        self.dfs(root, 0)\n",
    "        return root\n",
    "\n",
    "    def dfs(self, root: 'Node', dep):\n",
    "        if root is None:\n",
    "            return\n",
    "        if len(self.pre) == dep:\n",
    "            self.pre.append(root)\n",
    "        else:\n",
    "            self.pre[dep].next = root\n",
    "            self.pre[dep] = root\n",
    "        self.dfs(root.left, dep + 1)\n",
    "        self.dfs(root.right, dep + 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        queue = collections.deque([root])\n",
    "        \n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            prev = None\n",
    "            \n",
    "            for i in range(level_size):\n",
    "                node = queue.popleft()\n",
    "                \n",
    "                if prev:\n",
    "                    prev.next = node\n",
    "                \n",
    "                prev = node\n",
    "                \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        \n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            level = []\n",
    "            next_level = []\n",
    "            for node in queue:\n",
    "                level.append(node)\n",
    "                if node.left:\n",
    "                    next_level.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level.append(node.right)\n",
    "            queue = next_level\n",
    "            if len(level) > 1:\n",
    "                tem = level[0]\n",
    "                for i in level[1:]:\n",
    "                    tem.next = i\n",
    "                    tem = tem.next\n",
    "\n",
    "        # print(result)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            level = []\n",
    "            next_level = []\n",
    "            for node in queue:\n",
    "                level.append(node)\n",
    "                if node.left:\n",
    "                    next_level.append(node.left)\n",
    "                if node.right:\n",
    "                    next_level.append(node.right)\n",
    "            queue = next_level\n",
    "            if len(level) > 1:\n",
    "                tem = level[0]\n",
    "                for i in level[1:]:\n",
    "                    tem.next = i\n",
    "                    tem = tem.next\n",
    "\n",
    "        # print(result)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root==None:\n",
    "            return root\n",
    "        to_visit=deque([root])\n",
    "        while True:\n",
    "            to_link=deque()\n",
    "            if not to_visit:\n",
    "                break\n",
    "            cur=to_visit.popleft()\n",
    "            if cur.left:\n",
    "                to_link.append(cur.left)\n",
    "            if cur.right:\n",
    "                to_link.append(cur.right)\n",
    "            while to_visit:\n",
    "                Next=to_visit.popleft()\n",
    "                cur.next=Next\n",
    "                cur=Next\n",
    "                if cur.left:\n",
    "                    to_link.append(cur.left)\n",
    "                if cur.right:\n",
    "                    to_link.append(cur.right)\n",
    "            to_visit=to_link                \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        st=[root]\n",
    "\n",
    "        while st:\n",
    "            n=len(st)\n",
    "            for i in range(n):\n",
    "                node=st.pop(0)\n",
    "                if node.left:\n",
    "                    st.append(node.left)\n",
    "                if node.right:\n",
    "                    st.append(node.right)\n",
    "                if i!=n-1:\n",
    "                    node.next=st[0]\n",
    "        return root\n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        start = root\n",
    "        while start:\n",
    "            curr = start\n",
    "            self.last, self.start_next = None, None\n",
    "            while curr:\n",
    "                if curr.left:\n",
    "                    self.process(curr.left)\n",
    "                if curr.right:\n",
    "                    self.process(curr.right)\n",
    "                curr = curr.next\n",
    "            start = self.start_next\n",
    "        return root\n",
    "\n",
    "    def process(self, node):\n",
    "        if self.last:\n",
    "            self.last.next = node\n",
    "        self.last = node\n",
    "\n",
    "        if not self.start_next:\n",
    "            self.start_next = node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            last = None\n",
    "            for i in range(len(stack)):\n",
    "                tmp = stack.pop(0)\n",
    "                if tmp.left:\n",
    "                    stack.append(tmp.left)\n",
    "                if tmp.right:\n",
    "                    stack.append(tmp.right)\n",
    "                if last:\n",
    "                    last.next = tmp\n",
    "                last = tmp\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        deq = deque([root])\n",
    "        while deq:\n",
    "            last = None\n",
    "            n = len(deq)\n",
    "            for _ in range(n):\n",
    "                node = deq.popleft()\n",
    "                if node.left:\n",
    "                    deq.append(node.left)\n",
    "                if node.right:\n",
    "                    deq.append(node.right)\n",
    "                \n",
    "                if last:\n",
    "                    last.next = node\n",
    "                last = node\n",
    "        return root\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        queue = deque([root])\n",
    "        # 队列保持同一层元素\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            last = None\n",
    "            for _ in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                    # 让左指向右\n",
    "                if last:\n",
    "                    last.next = node\n",
    "                last = node\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            prev = None\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.pop()\n",
    "                if prev:\n",
    "                    prev.next = cur\n",
    "                prev =cur\n",
    "\n",
    "                if cur.left:\n",
    "                    queue.appendleft(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.appendleft(cur.right)\n",
    "\n",
    "  \n",
    "\n",
    "        return root   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None: return root\n",
    "        q = deque([root])\n",
    "\n",
    "        while q:\n",
    "            last = None\n",
    "            n = len(q)\n",
    "            for _ in range(n):\n",
    "                cur = q.popleft()\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "                if last:\n",
    "                    last.next = cur\n",
    "                last = cur\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        # pre = []\n",
    "        # def dfs(node: 'Node', depth: int) -> None:\n",
    "        #     if node is None:\n",
    "        #         return\n",
    "        #     if depth == len(pre):  # node 是这一层最左边的节点\n",
    "        #         pre.append(node)\n",
    "        #     else:  # pre[depth] 是 node 左边的节点\n",
    "        #         pre[depth].next = node  # node 左边的节点指向 node\n",
    "        #         pre[depth] = node\n",
    "        #     dfs(node.left, depth + 1)\n",
    "        #     dfs(node.right, depth + 1)\n",
    "        # dfs(root, 0)  # 根节点的深度为 0\n",
    "        # return root\n",
    "\n",
    "\n",
    "        if root is None:\n",
    "            return None\n",
    "        q = [root]\n",
    "        while q:\n",
    "            # 从左到右依次连接\n",
    "            for x, y in pairwise(q):\n",
    "                x.next = y\n",
    "            # 准备下一层的节点\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left:  q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return\n",
    "        # 层序遍历\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            # 当前层的节点数\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                # 当前节点\n",
    "                node = queue.pop(0)\n",
    "                # 当前节点右侧是否存在节点\n",
    "                if i < n - 1:\n",
    "                    node.next = queue[0]\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return root\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        res = []\n",
    "        queue = collections.deque([root])\n",
    "        # while queue:\n",
    "        #     prev = None\n",
    "        #     for i in range(len(queue)):\n",
    "        #         current = queue.popleft()\n",
    "        #         if prev:\n",
    "        #             prev.next = current\n",
    "        #         prev = current\n",
    "        #         if current.left:\n",
    "        #             queue.append(current.left)\n",
    "        #         if current.right:\n",
    "        #             queue.append(current.right)\n",
    "\n",
    "        while queue:\n",
    "            prev = None\n",
    "            level = []\n",
    "            for i in range(len(queue)):\n",
    "                current = queue.popleft()\n",
    "                level.append(current)\n",
    "                if current.left:\n",
    "                    queue.append(current.left)\n",
    "                if current.right:\n",
    "                    queue.append(current.right)\n",
    "            for j in range(len(level)-1):\n",
    "                level[j].next = level[j+1]\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return\n",
    "        layer = [root]\n",
    "        while len(layer) != 0:\n",
    "            new_layer = []\n",
    "            for node in layer:\n",
    "                if node.left != None:\n",
    "                    new_layer.append(node.left)\n",
    "                if node.right != None:\n",
    "                    new_layer.append(node.right)\n",
    "            for i in range(len(new_layer)-1):\n",
    "                new_layer[i].next = new_layer[i+1]\n",
    "            layer = new_layer\n",
    "        return root\n",
    "            \n",
    "            \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:return None\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                node.next = q[0] if i < size-1 else None\n",
    "                if node.left:q.append(node.left)\n",
    "                if node.right:q.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        cur = root\n",
    "        while cur:\n",
    "            nxt = dummy = Node()  # 下一层的链表\n",
    "            while cur:  # 遍历当前层的链表\n",
    "                if cur.left:\n",
    "                    nxt.next = cur.left  # 下一层的相邻节点连起来\n",
    "                    nxt = cur.left\n",
    "                if cur.right:\n",
    "                    nxt.next = cur.right  # 下一层的相邻节点连起来\n",
    "                    nxt = cur.right\n",
    "                cur = cur.next  # 当前层链表的下一个节点\n",
    "            cur = dummy.next  # 下一层链表的头节点\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        q = [root]\n",
    "        while q:\n",
    "            # 从左到右依次连接\n",
    "            for x, y in pairwise(q):\n",
    "                x.next = y\n",
    "            # 准备下一层的节点\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for node in tmp:\n",
    "                if node.left:  q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node(object):\n",
    "    def __init__(self, val=0, left=None, right=None, next=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution(object):\n",
    "    def connect(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        q = [root]\n",
    "        while len(q) and root != None:\n",
    "            prev = None\n",
    "            n = len(q)\n",
    "            while(n > 0):\n",
    "                cur = q.pop(0)\n",
    "                cur.next = prev\n",
    "                prev = cur\n",
    "                n = n - 1\n",
    "                if cur.right != None:\n",
    "                    q.append(cur.right)\n",
    "                if cur.left != None:\n",
    "                    q.append(cur.left)\n",
    "        return root\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        queue=[root]\n",
    "        while queue:\n",
    "            tmp=[]\n",
    "            for node in queue:\n",
    "                if node.left:tmp.append(node.left)\n",
    "                if node.right:tmp.append(node.right)\n",
    "            for i in range(len(tmp)-1):\n",
    "                tmp[i].next=tmp[i+1]\n",
    "            queue=tmp\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return root\n",
    "        list_ = [root]\n",
    "        while list_:\n",
    "            cycle_ = []\n",
    "            for i in range(len(list_)-1):\n",
    "                list_[i].next = list_[i+1]\n",
    "                if list_[i].left is not None:\n",
    "                    cycle_.append(list_[i].left)\n",
    "                if list_[i].right is not None:\n",
    "                    cycle_.append(list_[i].right)\n",
    "            if list_[-1].left is not None:\n",
    "                cycle_.append(list_[-1].left)\n",
    "            if list_[-1].right is not None:\n",
    "                cycle_.append(list_[-1].right) \n",
    "            list_ = cycle_\n",
    "        return root\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        queue = []\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            pre = None\n",
    "            for i in range(size):\n",
    "                node = queue.pop(0)\n",
    "                if pre :\n",
    "                    pre.next = node\n",
    "                pre = node\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return None\n",
    "        else:\n",
    "            queue = [root]\n",
    "            while queue:\n",
    "                p = None\n",
    "                arr= []\n",
    "                for node in queue:\n",
    "                    node.next = p\n",
    "                    p = node\n",
    "                    if node.right:\n",
    "                        arr.append(node.right)\n",
    "                    if node.left:\n",
    "                        arr.append(node.left)\n",
    "                queue = arr\n",
    "            return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            last = None\n",
    "            for _ in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                if last:\n",
    "                    last.next = node\n",
    "                last = node\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        # BFS\n",
    "        \n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            res = []\n",
    "            for _ in range(len(stack)):\n",
    "                node = stack.pop(0)\n",
    "                res.append(node)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            for i in range(0,len(res)-1):\n",
    "                res[i].next = res[i+1]\n",
    "            # res[-1].next = Node(\"#\")\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        queue = []\n",
    "        if root is None:\n",
    "            return None\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            last = None \n",
    "            for i in range(n):\n",
    "                node = queue.pop(0)\n",
    "                if i == n-1:\n",
    "                    node.next = None\n",
    "                else:\n",
    "                    node.next = queue[0]\n",
    "                if node.left :\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return root\n",
    "               \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "from queue import deque \n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None \n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for i in range(n):\n",
    "                if i+1 < n:\n",
    "                    q[i].next = q[i+1]\n",
    "                else:\n",
    "                    q[i].next = None \n",
    "            for i in range(n):\n",
    "                r = q.popleft()\n",
    "                if r.left is not None:\n",
    "                    q.append(r.left)\n",
    "                if r.right is not None:\n",
    "                    q.append(r.right)\n",
    "        return root \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return root\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        null = Node(101)\n",
    "        q.append(null)\n",
    "        while len(q) != 1:\n",
    "            node = q.popleft()\n",
    "\n",
    "            if node.val == 101:\n",
    "                q.append(null)\n",
    "                continue\n",
    "\n",
    "            if len(q) != 0 and q[0].val != 101:\n",
    "                node.next = q[0]\n",
    "            else:\n",
    "                node.next = None\n",
    "\n",
    "            if node.left :\n",
    "                q.append(node.left)  \n",
    "            if node.right :\n",
    "                q.append(node.right)\n",
    "               \n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if root is None:\n",
    "            return root\n",
    "        result = []\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            level_length = len(queue)\n",
    "            pre = None\n",
    "            for i in range(level_length):\n",
    "                cur = queue.popleft()\n",
    "                if pre:\n",
    "                    pre.next = cur\n",
    "                pre = cur\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            prev = None\n",
    "            for _ in range(size):\n",
    "                node = queue.popleft()\n",
    "                if prev:\n",
    "                    prev.next = node\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "                prev = node\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        pre=[]\n",
    "        def f(node,depth):\n",
    "            if not node:\n",
    "                return node\n",
    "            if len(pre) == depth:\n",
    "                pre.append(node)\n",
    "            else:\n",
    "                pre[depth].next = node\n",
    "                pre[depth] = node \n",
    "            f(node.left,depth+1)\n",
    "            f(node.right,depth+1)\n",
    "        f(root,0)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def get_value(self,root,level,result):\n",
    "        if root == None:\n",
    "            return\n",
    "        if level >=  len(result):\n",
    "            result.append([])\n",
    "        result[level].append(root)\n",
    "        self.get_value(root.left,level+1,result)\n",
    "        self.get_value(root.right,level+1 ,result)\n",
    "\n",
    "    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        result = []\n",
    "        self.get_value(root,0,result)\n",
    "        for nodes in result:\n",
    "            for index,node in enumerate(nodes):\n",
    "                if index + 1 < len(nodes):\n",
    "                    node.next = nodes[index + 1]\n",
    "                else:\n",
    "                    node.next = None\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        queue=collections.deque([root])\n",
    "        while queue:\n",
    "            n=len(queue)\n",
    "            for i in range(n):\n",
    "                node=queue.popleft()\n",
    "                if i <n-1:\n",
    "                    node.next=queue[0]\n",
    "                else:\n",
    "                    node.next=None\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)  \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        pre = []\n",
    "        def dfs(node: 'Node', depth: int) -> None:\n",
    "            if node is None:\n",
    "                return\n",
    "            if depth == len(pre):  # node 是这一层最左边的节点\n",
    "                pre.append(node)\n",
    "            else:  # pre[depth] 是 node 左边的节点\n",
    "                pre[depth].next = node  # node 左边的节点指向 node\n",
    "                pre[depth] = node\n",
    "            dfs(node.left, depth + 1)\n",
    "            dfs(node.right, depth + 1)\n",
    "        dfs(root, 0)  # 根节点的深度为 0\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        s = [root]\n",
    "        while s:\n",
    "            ns = []\n",
    "            for r in s:\n",
    "                if r.left:\n",
    "                    ns.append(r.left)\n",
    "                if r.right:\n",
    "                    ns.append(r.right)\n",
    "            \n",
    "            if len(ns) > 1:\n",
    "                for i in range(len(ns) - 1):\n",
    "                    ns[i].next = ns[i + 1]\n",
    "            \n",
    "            s = ns\n",
    "        \n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return\n",
    "        queue=collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            for i in range(1,len(queue)):\n",
    "                queue[i-1].next=queue[i]\n",
    "            for _ in range(len(queue)):\n",
    "                node=queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        \n",
    "        row_nodes = [root]\n",
    "        while row_nodes:\n",
    "            n = len(row_nodes)\n",
    "            tmp = []\n",
    "\n",
    "            for i in range(n):\n",
    "                node = row_nodes[i]\n",
    "\n",
    "                if i + 1 < n:\n",
    "                    node.next = row_nodes[i+1]\n",
    "                else:\n",
    "                    node.next = None\n",
    "\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "\n",
    "            row_nodes = tmp\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root == None:\n",
    "            return root\n",
    "        q = [root]\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            n = len(q)\n",
    "            if cur.left:\n",
    "                q.append(cur.left)\n",
    "            if cur.right:\n",
    "                q.append(cur.right)\n",
    "            for i in range(n):\n",
    "                t = q.pop(0)\n",
    "                cur.next = t\n",
    "                cur = t\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right) \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None \n",
    "        q = [root]\n",
    "        \n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                node = q.pop(0)\n",
    "                if i != size - 1:     #判断是否为最后一个元素\n",
    "                    node.next = q[0]\n",
    "                if node.left:\n",
    "                     q.append(node.left)\n",
    "                if node.right:\n",
    "                     q.append(node.right)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "from queue import deque \n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None \n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for i in range(n):\n",
    "                if i+1 < n:\n",
    "                    q[i].next = q[i+1]\n",
    "                else:\n",
    "                    q[i].next = None \n",
    "            for i in range(n):\n",
    "                r = q.popleft()\n",
    "                if r.left is not None:\n",
    "                    q.append(r.left)\n",
    "                if r.right is not None:\n",
    "                    q.append(r.right)\n",
    "        return root \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:return root\n",
    "        curr=[root]\n",
    "        while len(curr)>0:\n",
    "            next_lv=[]\n",
    "            for i in range(len(curr)):\n",
    "                if i!=len(curr)-1:\n",
    "                    curr[i].next=curr[i+1]\n",
    "                else:\n",
    "                    curr[i].next=None\n",
    "                if curr[i].left:next_lv.append(curr[i].left)\n",
    "                if curr[i].right:next_lv.append(curr[i].right)\n",
    "            curr=next_lv\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return root\n",
    "        queue=[root]\n",
    "        while queue:\n",
    "            size_queue=len(queue)\n",
    "            for i in range(size_queue):\n",
    "                node=queue.pop(0)\n",
    "                if i<size_queue-1:\n",
    "                    node.next=queue[0]\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        dic={}#dict()\n",
    "        #先前序遍历，将节点按照层数压入数组或字典，然后遍历数组或字典，将其收尾连接\n",
    "        def preorder(node,dic:'dict',layer=0):\n",
    "            if  not node:\n",
    "                pass\n",
    "                #return dic\n",
    "            else:\n",
    "                if layer not in dic:\n",
    "                    dic[layer]=[node] \n",
    "                else:\n",
    "                    dic[layer].append(node)\n",
    "                if  node.left:\n",
    "                    preorder(node.left,dic,layer+1)#dic=\n",
    "                if  node.right:\n",
    "                    preorder(node.right,dic,layer+1)#dic=\n",
    "                #return dic\n",
    "        preorder(root,dic,0)#dic=\n",
    "        i=0\n",
    "        if  dic:\n",
    "            while i in dic:\n",
    "                for j in range(len(dic[i])-1):\n",
    "                    dic[i][j].next=dic[i][j+1]\n",
    "                i+=1\n",
    "            return  dic[0][0]\n",
    "        else:\n",
    "            return None\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if not root:\n",
    "            return None\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                if i == 0:\n",
    "                    node = queue.popleft()\n",
    "                    nodePre = node\n",
    "                else:\n",
    "                    node = queue.popleft()\n",
    "                    nodePre.next = node\n",
    "                    nodePre = nodePre.next\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            nodePre.next = None\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        if root is None:\n",
    "            return None\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            for _ in range(len(q)-1):\n",
    "                node = q.popleft()\n",
    "\n",
    "                node1 = q.popleft()\n",
    "                node.next = node1\n",
    "                q.appendleft(node1)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            node = q.popleft()\n",
    "            node.next = None\n",
    "            if node.left: q.append(node.left)\n",
    "            if node.right: q.append(node.right)\n",
    "        return root\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.next = next\n",
    "\"\"\"\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def connect(self, root: 'Node') -> 'Node':\n",
    "        res = []\n",
    "        if not root:\n",
    "            return None\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            level = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                level.append(node)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            for i in range(len(level) - 1):\n",
    "                level[i].next = level[i + 1]\n",
    "            level[-1].next = None\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
